Many information systems need to transmit and store data securely, in a manner such that only authorized users may access it. One common approach to solving this problem is to use encryption. Encryption devices accept data to be encrypted along with an encryption key, and produce a resulting value known as a ciphertext. A system in possession of an associated decryption key may process the ciphertext to obtain the original data.
Most deployed encryption systems use one of two categories of encryption. Secret key (or “symmetric key”) encryption systems use the same key for both encryption and decryption of data. Public-key (or “asymmetric”) encryption systems use two associated keys, known as a “public key” and a “private key” (or “decryption key”), together known as a “key pair”. In these systems, exemplified by the RSA algorithm, the public key is useful only to encrypt data, and may thus be distributed widely. The corresponding private key may be held secret by the recipient and is used only to decrypt data. Public-key encryption solves one of the central problems arising in modern encryption systems: the ability to exchange information securely without a priori shared secrets.
In deployments today, the practical challenge for public-key encryption systems is the need to securely distribute public keys. Various approaches to solving this problem have been proposed. One approach is to use a Public Key Infrastructure (PKI), which includes trusted parties that certify the authenticity of various public keys. This approach has been successful for applications such as encrypted network communications (e.g., IPSec, SSL/TLS) and email (S/MIME).
However, limitations of the prior art may arise in data sharing scenarios. With standard public and symmetric key encryption systems, a transmitter must obtain the encryption key for each recipient to which it wishes to encrypt. For example, encrypting a record to all members of the “Accounting” group at a company requires that the encryptor obtain the public key for each member of the group prior to encrypting. Moreover, this encryption applies only to the members of the group at the time of encryption and if the membership of the group increases subsequent to encryption, new group members will be unable to decrypt the record.
With recent advances in public-key cryptography, a new approach for protecting data has arisen. Functional Encryption (FE) provides a new method for encrypting data in which encryptors do not encrypt to keys, or even to specific users, but instead embed a complex access predicate into the ciphertext or key itself. These predicates can be thought of as an access control program that enforces role-based or content-based controls on who may access content, and can possibly offer the decryptor different views of the encrypted content.
In ciphertext-policy Attribute-Based Encryption, a central authority provides recipients with keys that may embed textual attributes, e.g., “Accounting”, “Management” or “Top Secret”. Encryptors associate each ciphertext with an access policy might be computed as a Boolean formula over these textual attributes, e.g., “(Accounting AND Management) OR (Top Secret AND (Accounting OR Management))”. This formula specifies that the corresponding ciphertexts may only be decrypted by a key containing sufficient attributes to satisfy the formula associated with the ciphertext. In CP-ABE schemes, the decryption algorithm either produces the original message or fails to decrypt entirely.
In other, more general embodiments of FE, ciphertexts encrypt a message x and keys can be issued that embed any function F. Using the private key associated with F to decrypt an encryption of the message x, reveals the value F(x), that is the function F applied to the input x, and nothing else about x. Hence in Functional Encryption schemes, data access is self-enforcing from the cryptography and does not require a trusted mediator. More broadly, Functional Encryption provides a powerful capability for enforcing fine-grained access control.
The existence of ABE and general Functional Encryption schemes creates a new problem. In traditional public key and symmetric encryption schemes, there is generally a single decryption key corresponding to each encryption key that may have been used to generate a ciphertext. Hence, even where a decryption device stores multiple decryption keys, the decryptor is generally assured that at most one key will be useful in decrypting a given ciphertext. To simplify the decryption process, many encryption tools (e.g., PGP Mail, S/MIME) attach an associated key identifier to each ciphertext, in order to clearly indicate which decryption key should be used.
Existing encryption libraries rely fundamentally on this one-to-one mapping of encryption and decryption keys, and provide key management functions to store and manipulate decryption keys. For example, OpenSSL provides support for managing multiple keys on smart cards or hardware security modules, OpenPGP includes a mechanism for managing a set of uniquely identified keys on a client's machine via a keyring application, and the Keyczar library enables rotating and revoking keys on a client's system. These existing systems provide a keystore mechanism (such as a keyring) and enable decryption of ciphertexts by matching the fingerprint on a key within a keystore to the corresponding ciphertext.
In Functional Encryption deployments, on the other hand, there may exist multiple distinct decryption keys that are capable of decrypting a given ciphertext. For example, in a CP-ABE system, a ciphertext containing the policy “(Accounting AND Management) OR (Top Secret AND (Accounting OR Management))” may be decrypted by at least three decryption keys. This includes any key containing the attributes (“Accounting”, “Management”) or (“Accounting”, “Top Secret”) or (“Management”, “Top Secret”). Moreover, additional decryption keys may exist where other attributes are included in the key.
In the example of a KP-ABE system, a ciphertext may contain the attributes “Computer Science”, “Professor”, “Research”, and “Management”. Several decryption keys can be constructed with a variety of access policies that these attributes on the ciphertext could satisfy: (“Computer Science” AND “Professor”), ((“Research” OR “Management”) AND “Computer Science”) and so on. Similarly to CP-ABE, additional decryption keys may exist where other attributes are included in the policy associated with the key.
In the example of a MA-ABE system, a ciphertext may contain the policy such as “(Accounting AND Management) OR (Top Secret AND (Accounting OR Management))” similar to a single authority CP-ABE system. Constructing decryption keys in this setting may involve interacting with one or more key authorities. Not only can there be multiple distinct decryption keys to satisfy the policy, but also any number of possible authority combinations to produce a single decryption key.
In the example of a general FE system, a decryption key associated with function F and a decryption key associated with function G may decrypt a ciphertext encrypting message x to give two different values, F(x) and G(x).
Thus, a challenge in designing devices that implement Functional Encryption schemes including CP-ABE, KP-ABE, or MA-ABE is that devices may possess many different decryption keys that have some overlapping characteristics, or have different conditions for which they may be used. Moreover, different keys may yield different decryption times or possibly different views of the content. Therefore, upon receipt of a ciphertext, the user or device must select one key to use in decrypting the ciphertext.
One approach to selecting the decryption key is to simply attempt decryption of the ciphertext with each available key; however this is undesirable due to the high computational cost of these tests. Alternatively, the user might be asked to make this decision manually. However, requiring the user to make this decision presents a significant overhead for Functional Encryption. Moreover, at the end of this search process, users could find that they don't possess the necessary key to decrypt. In such cases, users would need to obtain the appropriate credentials from a key authority or key server. Alternatively, at the end of the search process, the user might discover multiple keys that will decrypt the ciphertext, but the decryption process may be more time consuming or resource-intensive when conducted with some keys than with others.
These scenarios highlight the challenges that end users have to overcome to manage their own Functional Encryption keys. Furthermore, this is coupled with the lack of existing services to help users manage their multiple Functional Encryption keys in practical deployments. Accordingly, there is a need for systems to identify an appropriate Functional Encryption decryption key, particularly in situations where multiple keys may exist that can correctly decrypt a ciphertext.